В этой задаче на проверку необходимо сдать текстовый файл с ответом. Входные данные вы можете скачать, нажав на кнопку с изображением стрелки справа-сверху рядом с кнопкой «Объявления жюри». Обратите внимание на увеличенные ограничения на $$$n$$$ в этой задаче по сравнению с предыдущей версией.
Давным-давно Егор и его друзья соревновались в решении задач по информатике. Все задачи с единственным ответом они на тот момент уже решили и придумали для себя новое испытание. У них была таблица $$$n \times n$$$, и они расставляли в ее клетки числа от 1 до $$$n^2$$$, каждое по одному разу. Расстановка считалась тем лучше, чем меньше в ней плохих пар соседних клеток. Пара соседних клеток считается плохой, если числа в этих клетках не являются взаимно простыми. Егор и его друзья уже выросли, так что теперь решать эту задачу предстоит вам.
Два числа называются взаимно простыми, если их наибольший общий делитель равен $$$1$$$.
Клетки считаются соседними, если они имеют общую сторону.
В первой строке задается количество наборов входных данных $$$T$$$. В этой задаче $$$T$$$ всегда равно 5.
В первой строке каждого описания набора входных данных дано одно целое число $$$n$$$ $$$(2 \le n \le 1000)$$$ — размер таблицы.
Для каждого набора входных данных выведите $$$n$$$ строк, в каждой из которых должно быть по $$$n$$$ целых чисел — выбранную таблицу.
Все числа от $$$1$$$ до $$$n^2$$$ должны встретиться в таблице ровно один раз.
Оценка за эту задачу — 40 баллов.
В этой задаче 1 тест, оценивающийся максимум в 40 баллов. Оценка за тест вычисляется как средняя оценка по наборам входных данных в тесте, умноженная на максимальный балл за тест. В этой задаче в единственном тесте — 5 наборов входных данных. Оценка за набор входных данных вычисляется по формуле:
$$$$$$grade = \operatorname{max}(1 - 1.7\cdot \frac{bad}{n^2}, 0)$$$$$$
где $$$bad$$$ и $$$n$$$ — количество плохих пар и размер таблицы соответственно.